package com.zwj.interview.BFS;


import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 给定一棵二叉搜索树和一个值k，请判断该二叉搜索树中是否存在值之和等于k的两个节点。假设二叉搜索树中节点的值均唯一。
 */
public class 两节点值之和等于目标值 {

    /**
     * 最直观的思路是利用哈希表保存节点的值。可以采用任意遍历算法遍历输入的二叉搜索树，
     * 每遍历到一个节点（节点的值记为v），就在哈希表中查看是否存在值为k-v的节点。如果存在，就表示存在值之和等于k的两个节点
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        //基于前序遍历（其实可以用任意的遍历顺序）
        Set<Integer> set = new HashSet();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            //先把树的一边压入栈中,我们这里将树的左边压入栈中
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //弹出一个进行比较
            cur = stack.pop();
            if (set.contains(k - cur.val)) {
                return true;
            }
            //不满足的话就需要将该数字放入set中，从树的另一边开始计算
            set.add(cur.val);
            cur = cur.right;
        }
        return false;
    }

}
